package com.xiaoyu.linkedArray;

/**
 * @program: DS_and_A
 * @description: 合并链表
 *
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * @author: YuWenYi
 * @create: 2021-04-26 20:33
 **/



public class MergeTwoLists {

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //解法一 ---------- >暴力法
        //用这个指针,来牢牢记录链表的第0个节点(自定义的第0个节点)!!
        ListNode preHead = new ListNode(-1);
        //这个指针用来操作数据!
        ListNode prev = preHead;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;   //用完指向下一个
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;   //这样就能只取l1的当前头部
        }
        prev.next = l1 == null ? l2 : l1;

        return preHead.next;
        // 解法二--->递归算法
        /*       if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }*/
    }
     /*
    * 首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。
    * 我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，
    * 直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，
    * 我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。
    * 否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。

      在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，
      它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，
      并返回合并链表即可。
    *
    * */
    //l1 = [1,2,4], l2 = [1,3,4]  --> [1,1,2,3,4,4]
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(2,new ListNode(4)));
        ListNode l2 = new ListNode(1,new ListNode(3,new ListNode(4)));

        ListNode res = mergeTwoLists(l1, l2);

        while (res.hasNext()){
            System.out.print(res.val+",");
            res = res.next;
        }
        System.out.println(res.val);
    }
}
